package com.le.tester.leetcode;

import com.google.common.collect.ImmutableList;
import net.bytebuddy.build.Plugin;

import java.util.*;

/**
 * 描述：账户合并
 */
public class AccountsMerger {


    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Integer> emailToIndex = new HashMap<>();
        Map<String, String> emailToName = new HashMap<>();
        int emailCount = 0;
        for (List<String> account : accounts) {
            //默认的数据格式第一个是名字
            String name = account.get(0);
            int size = account.size();
            for (int i = 1; i < size; i++) {
                //接下来获取到的都是email
                String email = account.get(i);
                //for中的if使得所有的值可以放进map
                if (!emailToIndex.containsKey(email)) {
                    //相同的email的index和name是会被覆盖的
                    emailToIndex.put(email, emailCount++);
                    emailToName.put(email, name);
                }
            }
        }
        System.out.println(emailToIndex.entrySet());
        System.out.println(emailToName.entrySet());

        //为parent数据赋值,已知多少个不同的email了
        UnionFind unionFind = new UnionFind(emailCount);
        for (List<String> account : accounts) {
            //以firstEmail来作为flag，第0个是名字
            String firstEmail = account.get(1);
            int firstIndex = emailToIndex.get(firstEmail);
            int size = account.size();
            //在account中的值有大于两个的基础上进行循环
            for (int i = 2; i < size; i++) {
                String nextEmail = account.get(i);
                int nextIndex = emailToIndex.get(nextEmail);
                unionFind.union(firstIndex, nextIndex);
            }
        }

        Map<Integer, List<String>> indexToEmails = new HashMap<>();
        for (String email : emailToIndex.keySet()) {
            int index = unionFind.find(emailToIndex.get(email));
            List<String> account = indexToEmails.getOrDefault(index, new ArrayList<>());
            account.add(email);
            indexToEmails.put(index, account);
        }

        List<List<String>> result = new ArrayList<>();
        for (List<String> emails : indexToEmails.values()) {
            Collections.sort(emails);
            String name = emailToName.get(emails.get(0));
            List<String> account = new ArrayList<>();
            account.add(name);
            account.addAll(emails);
            result.add(account);
        }

        return result;
    }

    public static void main(String[] args) {
        AccountsMerger accountsMerger = new AccountsMerger();
        List<List<String>> accounts = new ArrayList<>();
        accountsMerger.add(accounts, "John", "johnsmith@mail.com", "john00@mail.com");
        accountsMerger.add(accounts, "John", "johnnybravo@mail.com");
        accountsMerger.add(accounts, "John", "johnsmith@mail.com", "john_newyork@mail.com");
        accountsMerger.add(accounts, "Mary", "mary@mail.com");


        System.out.println(accountsMerger.accountsMerge(accounts));
    }

    public void add(List<List<String>> account, String... ele) {
        List<String> list = new ArrayList<>(Arrays.asList(ele));
        account.add(list);
    }

}

class UnionFind {
    int[] parent;

    public UnionFind(int i) {
        parent = new int[i];
        for (int j = 0; j < i; j++) {
            parent[j] = j;
        }
    }

    //index1==0,index2==1
    public void union(int index1, int index2) {
//        int parentFindIndex2 = parent[find(index2)];
//        int findIndex1 = find(index1);
//        System.out.println("parentFindIndex2:" + parentFindIndex2);
//        System.out.println("findIndex1:" + findIndex1);
        //先执行了左边的find,再者执行了右边，最好后还是会进行find的执行
        //返回的值会是parent[index]=0,在account.size()>2
        parent[find(index2)] = find(index1);
        //测试数据之后parent最后的数组值应该是parent:[0, 0, 2, 0, 4]
    }

    public int find(int index) {
        if (parent[index] != index) {
            parent[index] = find(parent[index]);
        }
        return parent[index];
    }

}
